#include "is_valid.h"
#include "oper.h"
#include "tree.h"

#define VALUE_BYTE_NUMS (sizeof(u64_s) - 1)
#define VALUE_BIT_NUMS (VALUE_BYTE_NUMS * 8)

// 对每个节点数不超过7的二叉树，其计算的一个惟一的值结构体。
typedef struct {
	u64_s value : VALUE_BIT_NUMS;
	u64_s byte_nums : 8;
} tree_value_t;

static u64_s _get_value(tree_value_t value) {
	union {
		tree_value_t t;
		u64_s u;
	} tu = {
		.t = value,
	};
	return tu.u;
}

// 根据结点和左右子树的值，计算树的值。
static tree_value_t _cal_value(oper_e oper, const tree_value_t* left_value_p,
			       const tree_value_t* right_value_p) {
	u32_s left_byte_nums = left_value_p->byte_nums;
	u32_s right_byte_nums = right_value_p->byte_nums;
	tree_value_t value_stru = {
		.byte_nums = left_byte_nums + right_byte_nums + 1,
		// value计算较复杂，后面再填。
	};
	u64_s com_value = left_value_p->value |
			  (right_value_p->value << (left_byte_nums * 8));
	u64_s oper_value = oper;
	u64_s value = oper_value | (com_value << 8);
	value_stru.value = value;
	return value_stru;
}

typedef struct {
	tree_value_t value;
	tree_value_t right_value;
} cal_value_mid_result;

static cal_value_mid_result _is_sub_tree_valid_cal_value(const tree34_t* tree_p,
							 const node_t* node_p) {
	static const cal_value_mid_result invalid_result = {};

	// 叶子节点直接返回有效
	if (!node_is_oper(tree_p, node_p)) {
		u64_s num = node_get_num(tree_p, node_p);
		cal_value_mid_result result = {
			.value.value = num,
			.value.byte_nums = 1,
			.right_value = {},
		};
		return result;
	}

	sub_nodes_t sub = node_get_sub(tree_p, node_p);
	const node_t* left_p = sub.left_p;
	const node_t* right_p = sub.right_p;

	oper_e oper = node_get_oper(tree_p, node_p);
	oper_dmd_s oper_dmd = oper_get_dmd(oper);
	b32_s has_prev = 0;
	tree_value_t prev_value_struct;
	b32_s is_left_oper = node_is_oper(tree_p, left_p);
	b32_s is_right_oper = node_is_oper(tree_p, right_p);
	oper_e left_oper;
	oper_e right_oper;
	if (is_left_oper) {
		left_oper = node_get_oper(tree_p, left_p);
	}
	if (is_right_oper) {
		right_oper = node_get_oper(tree_p, right_p);
	}

	// 右子结点不能是同类运算（加减一类，乘除一类）（强制要求同类运算从左到右）
	if (is_right_oper) {
		oper_dmd_s right_dmd = oper_get_dmd(right_oper);
		if (oper_dmd.is_mul_div == right_dmd.is_mul_div) {
			return invalid_result;
		}
	}

	// 如果左子结点是同类运算（加减一类，乘除一类），
	// 不能左子结点是down（减或除）而当前结点是up（加或乘）。
	// （强制要求加完才减、乘完才除）
	if (is_left_oper) {
		oper_dmd_s left_dmd = oper_get_dmd(left_oper);
		if (oper_dmd.is_mul_div == left_dmd.is_mul_div &&
		    left_dmd.is_down && !oper_dmd.is_down) {
			return invalid_result;
		}
	}

	// 左子树必须合法
	cal_value_mid_result left_result =
		_is_sub_tree_valid_cal_value(tree_p, left_p);
	tree_value_t left_value_struct = left_result.value;
	u64_s left_byte_nums = left_value_struct.byte_nums;
	if (left_byte_nums == 0) {
		return left_result;
	}

	// 右子树必须合法
	cal_value_mid_result right_result =
		_is_sub_tree_valid_cal_value(tree_p, right_p);
	tree_value_t right_value_struct = right_result.value;
	u64_s right_byte_nums = right_value_struct.byte_nums;
	if (right_byte_nums == 0) {
		return right_result;
	}

	// 如果和左子结点是同一运算，则右子结点的value不能大于左子结点的右子结点的。
	// 如果本结点是up（加或乘），右子结点的value不能大于左子结点的。
	// （强制要求先操作value大的再操作value小的）
	if (is_left_oper && left_oper == oper) {
		has_prev = 1;
		prev_value_struct = left_result.right_value;
	} else if (!oper_dmd.is_down) {
		has_prev = 1;
		prev_value_struct = left_result.value;
	}
	if (has_prev) {
		u64_s right_value = _get_value(right_value_struct);
		u64_s prev_value = _get_value(prev_value_struct);
		if (right_value > prev_value) {
			return invalid_result;
		}
	}
	tree_value_t value_struct =
		_cal_value(oper, &left_value_struct, &right_value_struct);
	cal_value_mid_result result = {
		.value = value_struct,
		.right_value = right_value_struct,
	};
	return result;
}

// 对外提供：cal_tree_value()
// 返回0说明不合法，应丢弃。
u64_s cal_tree_value(const tree34_t* tree_p) {
	const node_t* head_p = tree_get_head(tree_p);
	cal_value_mid_result result =
		_is_sub_tree_valid_cal_value(tree_p, head_p);
	if (result.value.byte_nums) {
		return _get_value(result.value);
	}
	return 0;
}
